package com.ly.algorithm.leetcode.tree;

/**
 * @Classname Problem114
 * @Description
 *
 * 例如，给定二叉树
 *
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 * 将其展开为：
 *
 * 1
 *  \
 *   2
 *    \
 *     3
 *      \
 *       4
 *        \
 *         5
 *          \
 *           6
 *
 *
 * @Date 2020/12/22 15:58
 * @Author 冷心影翼
 */
public class Problem114 {

	public static void main(String[] args) {
		Solution114 solution114 = new Solution114();
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.left.left = new TreeNode(3);
		root.left.right = new TreeNode(4);
		root.right = new TreeNode(5);
		root.right.right = new TreeNode(6);
		solution114.flatten(root);
		System.out.println(root.right.val);
	}

}


class Solution114 {
	public void flatten(TreeNode root) {
		if(root == null )
			return;
		flatten(root.left);
		flatten(root.right);
		TreeNode left = root.left;
		TreeNode right = root.right;
		// 2、将左子树作为右子树
		root.left = null;
		root.right = left;

		// 3、将原先的右子树接到当前右子树的末端
		TreeNode p = root;
		while (p.right != null) {
			p = p.right;
		}
		p.right = right;
	}
}